Hessenberg 分解

阐述

对于 $n\times n$ 方阵 $A$ ，其 Hessemberg 分解为

A=QHQ^*

其中， $H$ 是上 Hessenberg 阵，也就是在上三角矩阵的基础上最多多一行对角线下的元素。

这个分解可以在 $\Theta(m^3)$ 的复杂度内完成。

矩阵 $H$ 和原来的矩阵 $A$ 是相似的，也就是说它们有同样的本征值。

解线性方程和计算 QR 分解都只需要 $\Theta(m^2)$ 步。

另外，如果 $A$ 是 Hermite 矩阵，那么 $H=H^*$ ，说明 $H$ 是三对角、Hermite 矩阵，计算只需要 $\Theta(m)$ 步。